Computer science eponyms |
您所在的位置：网站首页 › cannon's algorithm › Computer science eponyms |
|
Computer science needs more eponyms, in the vein of Mordenkainen. Collect them all, and impress your friends! I might make a project one day of summarizing these entries. Explicitly not included in this list are: general logic (Peano and Presburger arithmetic), mathematical entities not primarily associated with computer science (Markov's inequality, Chapman-Kolmogorov equation, Young tableaux), physical theories to which computer science is merely applied (Navier-Stokes equations, Taylor-Couette flow), nor statistical entities not primarily associated with computer science (Ziph's Law, Pareto efficiency). Explicitly included are: terms from computer engineering (Mead-Conway rules, Ling adders). UPDATE the threshold for inclusion is now: De Morgan's Laws. If you're not at least as computer sciency as De Morgan's Laws, you ain't gettin' in. Dank 12:25, 3 October 2011 (CDT) Aanderaa–Rosenberg Conjecture suggests that non-trivial monotonicity properties of undirected graphs can only be solved by Ω(N2) algorithms on N vertices (these are all evasive decision trees on all possible edges) Adam7 Algorithm is a 2D, 7-pass interlacing scheme optionally used by PNG due to Adam Costello the Adler-32 checksum trades reliability for speed relative to CRCs of the same length, and is included in Mark Adler's zlib Adleman's Theorem states that P/poly contains all problems solvable in randomized polynomial time Adelson-Velskii-Landis Trees are self-height-balancing binary search trees, optimizing for lookup over modification viz. red-black trees Aho-Corasick Algorithm extends the Knuth-Morris-Pratt automaton to match multiple strings in one pass of a text Akra-Bazzi Method generalizes the "master method" of Bentley, Haken, and Saxe for subproblems of significantly different size Amdahl's Law Andersen's Algorithm Angluin's algorithm Arikan's PAC Codes aka polarization-adjusted convolutional polar coding outperform CRC-aided and purely convolutional polar codes, approaching the theoretical channel capacity for short blocklengths. Armstrong's axioms are a set of inference rules which generate all functional dependencies of a relational database. Similarly, an Armstrong relation satisfies all the functional dependencies in the closure F+ (and only those dependencies). Backus-Naur Form Bajard-Kla-Muller algorithm Ball-Larus Heuristics the Banerjee test can demonstrate the absence of control flow dependencies in certain types of loops Barendregt convention Barendregt-Geuvers-Klop Conjecture Barnes-Hut simulation the Barton-Nackman trick is an idiom in C++ effecting restricted template expansion Baskett, Chandy, Muntz and Palacios network Batcher's Odd-Even Merge Bayer Filter mosaics arrange RGB color filters on a square array of photosensors, and are used in a majority of single-chip image sensors. It uses twice as many green sensors as red or blue, to mimic the physiology of the human eye Bélády's algorithm is the theoretically best cache-replacement algorithm, one which discards information that will not be needed until the furthest time into the future (this is not usually knowable) Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns, especially when using FIFO page replacement Bell-La Padula model the Bellman Equation specifies for a problem the necessary condition for optimality of dynamic programming Bellman-Ford Algorithm Beneš network Bentley-Ottman Algorithm Berlekamp-Massey Algorithm Berman–Hartmanis conjecture Bernstein chaining Bernstein conditions Biba Integrity Model Blinn-Phong shading Blom's Scheme Bloom filter Bluestein's FFT Blum's axioms Blum's Speedup Theorem Blum-Blum-Shub random number generator Boehm-Demers-Weiser garbage collector the Boolean data type takes on values of true or false, as do variables in George Boole's algebra Booth's Algorithm Borůvka's Algorithm Bowyer-Watson Algorithm Boyer-Moore Algorithm Bremermann's Limit Brent's Adder is logn + O(log1/2n) depth and O(nlg n) size Brent's Algorithm detects cycles using two pointers, and finds the length of the cycle directly Brent's Method is a hybrid root-finding algorithm combining bisection, the secant method, and inverse quadratic interpolation Brent's Theorem aka Brent's Law states that p < N processors can simulate N in T_p ≤ T_N + (T_1 - T_N)/p Bresenham's Algorithm Brewer's Theorem Brodal Queue Broder's Method Bron-Kerbosch Algorithm Brooks-Iyengar Algorithm Buchberger Algorithm Burrows-Wheeler Transform Buzen's Algorithm Callahan-Koblenz algorithm Cannon's Algorithm Cantor-Zassenhaus Algorithm Carmack's Reverse Catmull-Clark subdivision surfaces Chaff Algorithm Chaitin's algorithm Chaitin's Constant Chaitin-Briggs algorithm Chaitin–Kolmogorov random numbers Chakravala's Algorithm Chan's Algorithm Chandy-Lamport Algorithm the Chang-Roberts Algorithm elects leaders for distributed systems. Cheney's Algorithm Chew's Second Algorithm Chien search Cholesky decomposition expands Hermitian positive-definite matrices into products of a lower triangular matrix and its conjugate transpose. solved using the Cholesky–Crout and Cholesky–Banachiewicz algorithms. Chomsky Hierarchy Chomsky Normal Form Chomsky-Schützenberger theorem Christofides Algorithm Church encoding Church-Rosser Theorem Church-Turing Thesis Clos network Cobham Axioms Cobham's thesis Cocke-Younger-Kasami Algorithm Cohen-Sutherland algorithm Coffman conditions enumerate the four conditions necessary and sufficient for deadlock within a system (mutual exclusion, hold-and-wait, a lack of preemption, and circular wait) Commentz-Walter Algorithm Conway's Law Cook reduction the Cook-Levin Theorem (sometimes just Cook Theorem) proves that the Boolean satisfiability problem is NP-complete. the Cooley-Tukey Algorithm is the workhorse algorithm for Fast Fourier Transforms. the Coppersmith-Winograd Algorithm multiplied matrices in the least time complexity from 1990-2010, and used the "laser method" employed by all improvements since. Craig, Landin and Hagersten lock Cranfield method (preconditioned) Crank–Nicolson Algorithm Crusader’s Convergence Algorithm Curry-Howard correspondence Dadda Multiplier Damerau-Levenshtein distance Damm Algorithm Davis-Putnam Algorithm Davis-Putnam-Logemann-Loveland Algorithm De Bruijn presentation De Bruijn string Dekker's Algorithm Delaunay's Triangulation Dennard Scaling Deutsch gate Diffie-Hellman Key Exchange Dijkstra's Algorithm Dinic's Algorithm DiVincenzo's criteria specify conditions necessary for a quantum computer Dolev's Algorithm Doo-Sabin subdivision surface Duff's Device Dyck Language Earle latch Earley Parser Edholm's law predicts doubling of bandwidth every 18 months across wireless, nomadic, and wired networks (and is getting some rather heavy lift from Moore's Law IMHO) Edmonds's matching algorithm constructs maximum matchings on graphs in O(|E||V|²) Edmonds-Karp Algorithm ElGamal encryption ElGamal signatures van Emde Boas trees Sieve of Eratosthenes Euclid's Algorithm Fagin's Theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP Falk diagrams graph various performance counters against time (typically expressed in cycles) Faugère F5 algorithm Fenwick trees support efficient update of elements and calculate prefix sums in a table of numbers Fiat-Shamir Heuristic Fibonacci Heap Fisher-Yates shuffle Flajolet-Martin algorithm Fletcher's Checksum Floyd's Algorithm Floyd-Steinberg dithering Flynn Taxonomy Ford-Fulkerson Algorithm Fortune's Algorithm Fox's Algorithm Fredkin gate Friedberg-Muchnik Theorem Fruchterman-Reingold heuristic Fürer's algorithm multiplies two n-digit numbers in O(nlgn*2O(lg*n)) Gabbay's separation theorem Gabow's Algorithm Gal's Accurate Tables Gale-Church Algorithm Gale-Shapley algorithm Gilbert-Johnson-Keerthi Algorithm Girard's Paradox Girvan-Newman Algorithm Givens rotation Glushkov Automata Goldreich-Goldwasser-Halevi scheme The weighted Gomory-Hu Tree of an undirected graph with capacities G represents the minimum s-t cuts for all s-t pairs in G, and is computable via |V|-1 maximum flow problems. Gordon–Newell theorem Gosper's Hack Gosper's Hypergeometric Algorithm Gosper's Loop Detection Algorithm Gouraud shading The Graham Scan solves for the convex hull of a set of points in O(NlgN). The Graham-Andrew Algorithm modifies the Graham Scan to solve for convex hulls in O(N) best case. Graham-Denning Model Gram–Schmidt process Gray codes Greibach Normal Form Grover's Algorithm Grzegorczyk hierarchy Guruswami-Sudan Algorithm Gustafson's Law Gutmann's Method is a 35-phase recipe for destroying data on ferromagnetic drives. Guttman-Rosler transform Hamiltonian path problem Hamming code Hamming distance Heckel's algorithm isolates changes between files, and is the basis for diff CACM 1978 Hennessy-Milner Logic Herlihy's wait-free hierarchy Hindley-Milner type system Hirschberg's Algorithm Hoare logic Holevo's Theorem Holland's schema theorem Hong-Kung bound Hopcroft-Karp Algorithm Hopfield net Horn clauses Hough transform Householder transformation Huet's Zipper Huffman coding Hunt-McIlroy Algorithm Iliffe vector Immerman–Szelepcsényi theorem Jackson network Jackson's theorem Jaro-Winkler distance Jefferson's Time Warp Jelinek-Mercer smoothing Jensen's Device Johnson's Algorithm the Jonker-Volgenant Algorithm improves Kuhn's Algorithm to solve the assignment problem in O(n³), Jonker-Volgenant 1987 Kabsch Algorithm Kadane's Algorithm Kahan Summation Algorithm Kahn's Algorithm topologically sorts a graph in O(|V| + |E|), Kahn 1962 Kannan's Theorem Karatsuba's Algorithm multiplies two n-digit numbers using nlog23 single-digit mults Karger's Algorithm Karn's algorithm extracts accurate TCP RTT measures, Karn-Partridge 1987 Karmarkar's algorithm Karnaugh map Karp reduction Karp-Flatt metric Karp-Lipton Theorem Kamada-Kawai algorithm Kernighan-Lin algorithm Kirkpatrick-Seidel Algorithm Kleene Closure Kleene Plus Kleene Star Kleene–Rosser Paradox Kneser-Ney smoothing Knuth Shuffle Knuth-Morris-Pratt Algorithm Koenig Lookup Kohonen Algorithm Kohonen network Kolmogorov complexity Koomey's Law Kosaraju's Algorithm Krapchenko's Adder is an improvement over Brent's Adder, linear (3n + 6*2m, m=ceil(lg n)) in size and logn + O(log1/2n) depth (m + 7(2m)1/2+16, m = ceil(lg n)). Kruskal's Algorithm Kryder's Law asserted that areal density doubles every thirteen months (this has not been true for some time). Also known as the Kryder rate. Kuhn's Algorithm (also known as Kuhn-Munkres) solves the assignment problem in polynomial time, Kuhn 1955 Kung-Leiserson systolic array Kuroda Normal Form Ladner's Theorem Lamport's Bakery Algorithm Lamport's Logical Clock Lamport's Hash Lamport timestamps Lee-Seung algorithm Lehmer random number generator Lehmer's GCD Algorithm Lempel-Ziv-Welch compression Levenshtein automaton Levenshtein distance Levin reduction Liang-Barsky algorithm Lin-Kernighan Heuristic Linde-Buzo-Gray algorithm Ling adders Liskov's Substitution Principle Lloyd's algorithm Loop subdivision surfaces Loss-DiVincenzo machines are quantum computers based off electron spin as confined to quantum dots Luby's algorithm Luhn Algorithm Luleå Algorithm Maekawa's Algorithm Mahaney's Theorem Manning algorithm Margolus gate Marzullo algorithm McFarling-style branch predictor Mead-Conway Rules Mealy machine Mellor-Crummey and Scott lock Merkle–Damgård construction The Metropolis-Hastings algorithm for MCMC obtains samples from a probability distribution that is difficult to directly sample Miller-Rabin Primality Test Minsky-Fenichel-Yochelson Algorithm Montgomery reduction Moore machine Moore's Law Morgensen-Scott encoding Möller-Trumbore algorithm Nagle's algorithm Nassi-Shneiderman diagram Needham-Schroeder Protocol Needleman-Wunsch Algorithm Neuman-Stubblebine Protocol von Neumann architecture aka stored-program architecture keeps instructions in the same memory as data (as opposed to Harvard architecture, which keeps the two distinct). Popularized by von Neumann, but largely based on Eckert and Mauchly's work on the ENIAC. Nevill-Manning algorithm Nick's Class Nielsen's law predicts slower growth for home bandwidth than computing power, suggesting that user experience will remain bandwidth-bound Nielsen's usability heuristics are ten (rather debatable) guidelines forming a usability heuristic for interface design Nisan's Generator Ogden's lemma extends the pumping lemma to context-free languages Ousterhout's dichotomy/fallacy a taxonomy of systems vs scripting languages Otway-Rees Protocol Paeth-Tanaka Algorithm rotates images via a method of three shears Paeth Filter performs 2D image compression in PNG PageRank Algorithm Peterson's Algorithm Petri nets Petrick's method Phong shading Plotkin's Sticky Bit Pollaczek–Khinchine formula Pollard's Kangaroo Algorithm Pollard's ρ Algorithm aka Pollard's rho Algorithm factors integers in running time expected to be proportional to the square root of the smallest prime factor of the number being factored Popek-Goldberg virtualization requirements Post's correspondence problem Post's Lattice is the lattice of all clones on {0,1}, ordered by inclusion. It is used to prove sets of connectives to be functionally complete (e.g. NAND and NOR both generate functionally complete Boolean algebras). Postel's Law Prim's Algorithm Proebsting's Law claims that compiler technology doubles computing power every 18 years Prüfer Coding Prüfer Sequence Quines Quine-McLuskey algorithm Rabin Automata Rabin's Information Dispersal Algorithm Rabin-Karp Algorithm Rader-Brenner Algorithm Radovic-Hagersten lock Raymond's Algorithm Reed-Muller code Reed-Solomon correction code Reingold's logspace Algorithm Ricart-Agrawala Algorithm Rice's Theorem Rice-Shapiro Theorem Risch Algorithm Rivest-Shamir-Adleman Algorithm Rocchio's Algorithm classifies information relevance using nearest centroids Ruppert's Algorithm Sattolo's Algorithm generates a 1-cyclic derangement of an array (a permutation such that every element ends up in a new position) Savitch's Theorem Schensted Algorithm Schlick's approximation The Schönhage–Strassen algorithm multiplies two n-digit numbers in O(nlgnlglgn) bit complexity using FFTs Schoof's Algorithm Schreier-Sims Algorithm Schwartzian transform Sethi-Ullman Algorithm Shamir's Secret Sharing Scheme Shamos-Hoey Algorithm Shar's Algortihm is a variation on the uniform binary search of Knuth. Shor's Algorithm Sipser–Lautemann theorem Smith's Algorithm hashes the program counter to n bimodal (saturating) k-bit counters for dynamic branch prediction (1981) Smith-Waterman algorithm Solomonoff-Levin distribution Steensgaard's Algorithm Stehlé-Zimmermann algorithm Steiner tree problems are a class of combinatorial optimization problems involving determining the optimal interconnect of a graph under some objective function. Steinhaus-Johnson-Trotter algorithm Strassen's Algorithm Suurballe's Algorithm Sweeney-Robertson-Tocher division algorithm Tarjan's Algorithm Tarjan's Dynamic Tree Tarjan's Least Common Ancestors Algorithm The nondeterministic Tarski–Kuratowski algorithm produces an upper bound for the complexity of a given formula in the arithmetical hierarchy and analytical hierarchy. Thompson Automata Timsort Toda's theorem Todd–Coxeter algorithm the Toffoli gate aka CCNOT is a 3-to-3 universal reversible gate (all other reversible gates can be constructed from it). there is no smaller universal set of reversible gates (the only reversible gates in 1 or 2 inputs are identity, NOT, and CNOT). Tomasulo's Algorithm Tonelli-Shanks Algorithm The Toom-Cook Algorithm multiplies two n-digit numbers using nlog(5)/log(3) single-digit mults Tupper's self-referential formula Turing Degree Turing Machines the Turing Test, originally the "imitation game", was proposed by Turing as a means of evaluating conversational artificial intelligence via questions-and-answers on a text channel. Ukkonen's Algorithm Valiant-Vazirani Theorem Van Jacobson Channels Van Wijngaarden Grammars Verhoeff Algorithm Viola-Jones face detection Viterbi algorithm Volder's algorithm Wagner-Fischer Algorithm Wallace Multiplier Wallace tree Warnsdorff's Algorithm Welford's Algorithm is a stable online algorithm for computing mean and estimated variance The Williams State Machine is a common parsing automaton for DEC virtual terminal input Winograd's Algorithm Witten-Bell smoothing Wu's Line Algorithm Wu-Manber Algorithm Wyllie's List Ranking Yao's Principle Yeh's Algorithm is a two-level adaptive training algorithm designed by Yeh and Patt in 1991. A branch history register is used to maintain branch behavior for a specific pattern of branch history, and 4-bit counters are used for each BTB set. Zhu-Takaoka Algorithm Zimmermann-Sassaman key-signing protocol Zobrist hashing |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |